|
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: : Otherwise, ''q'' is called a quadratic nonresidue modulo ''n''. Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers. ==History, conventions, and elementary facts== Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries proved some theorems〔Lemmemeyer, Ch. 1〕 and made some conjectures〔Lemmermeyer, pp 6–8, p. 16 ff〕 about quadratic residues, but the first systematic treatment is § IV of Gauss's ''Disquisitiones Arithmeticae'' (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that, if the context makes it clear, the adjective "quadratic" may be dropped. For a given ''n'' a list of the quadratic residues modulo ''n'' may be obtained by simply squaring the numbers 0, 1, …, ''n'' − 1. Because ''a''2 ≡ (''n'' − ''a'')2 (mod ''n''), the list of squares modulo ''n'' is symmetrical around ''n''/2, and the list only needs to go that high. This can be seen in the table below. Thus, the number of quadratic residues modulo ''n'' cannot exceed ''n''/2 + 1 (''n'' even) or (''n'' + 1)/2 (''n'' odd).〔Gauss, DA, art. 94〕 The product of two residues is always a residue. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quadratic residue」の詳細全文を読む スポンサード リンク
|